// import { defaultEquals } from "./util.js";
// const defaultEquals = require('./lib/util')

// 默认的相等性比较函数
function defaultEquals(a, b) {
  return a === b;
}

// 表示我们想要添加到链表中的项
class Node {
  constructor(element) {
    this.element = element; // 加入链表元素的值
    this.next = undefined; // 指向链表中下一个元素的指针
  }
}

/**
 * 普通链表：在链表中，一个节点只有链向下一个节点的链接
 */

class LinkenList {
  constructor(equalsFn = defaultEquals) {
    this.equalsFn = equalsFn;
    this.count = 0; // 来存储链表中的元素数量
    this.head = undefined;
  }

  // 向链表尾部添加一个新元素。
  push(e) {
    const node = new Node(e);
    let current;
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next != null) {
        // 获得最后一项
        current = current.next;
      }
      current.next = node; // 将其 next 赋为新元素，建立链接
    }
    this.count++;
  }

  // 移除链表元素
  removeAt(index) {
    // 检查越界值
    if (index >= 0 && index < this.count) {
      let current = this.head;
      // 移除第一项
      if (index === 0) {
        this.head = current.next;
      } else {
        let previous = this.getElementAt(index - 1);
        current = previous.next;
        // 将 previous 与 current 的下一项链接起来：跳过 current，从而移除它
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  //  循环迭代链表直到目标位置
  getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      let current = this.head;
      for (let i = 0; i < current && current != null; i++) {
        current = current.next;
      }
      return current;
    }
    return undefined;
  }

  // 在任意位置插入一个元素
  insert(e, index) {
    if (index >= 0 && index <= this.count) {
      let node = new Node(e);
      if (index === 0) {
        // 在第一个位置添加
        let current = this.head;
        node.next = current;
        this.head = node;
      } else {
        let previous = this.getElementAt(index - 1);
        let current = previous.next;
        node.next = current;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  // 返回一个元素的位置
  indexOf(e) {
    let current = this.head;
    for (let i = 0; i < this.count && current != null; i++) {
      if (this.equalsFn(e, current.element)) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }
  // 从链表中移除元素
  remove(e) {
    let index = this.indexOf(e);
    return this.removeAt(index);
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.size() === 0;
  }

  getHead() {
    return this.head;
  }

  toString() {
    if (this.head == null) return "";
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }
}

let linked = new LinkenList();
linked.push(1);
linked.push(2);
console.log(linked.removeAt(0));
linked.push(3);
console.log(linked.toString(0));

/**
 *  双向链表：在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素
 */

class DoublyNode extends Node {
  constructor(element, next, prev) {
    super(element, next);
    this.prev = prev;
  }
}

class DoublyLinkedList extends LinkenList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
    this.tail = undefined;
  }

  // 在任意位置插入新元素
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;
      if (index === 0) {
        if (this.head == null) {
          // 新增的
          this.head = node;
          this.tail = node;
        } else {
          node.next = this.head;
          current.prev = node; // 新增的
          this.head = node;
        }
      } else if (index === this.count) {
        // 新增的
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        node.next = current;
        previous.next = node;
        current.prev = node; // 新增的
        node.prev = previous; // 新增的
      }
      this.count++;
      return true;
    }
    return false;
  }

  // 从任意位置移除元素
  removeAt(index) {
    if (index >= 0 && index <= this.count) {
      let current = this.head;
      if (index === 0) {
        this.tail = current.next;
        // 如果只有一项，更新 tail  // 新增的
        if (this.count === 1) {
          this.tail = undefined;
        } else {
          this.head.prev = undefined;
        }
      } else if (index === this.count - 1) {
        // 最后一项 // 新增的
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        current = this.getElementAt(index);
        const previous = current.prev;
        previous.next = current.next; // 将 previous 与 current 的下一项链接起来——跳过 current
        current.next.prev = previous; // 新增的
      }
      this.count--; 
      return current.element;
    }
    return undefined;
  }
}
